#leetcode题目5：最长回文子串
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n^2)
#解题思路：动态规划，中心扩展法
#当前解法参考b站

class Solution:
    def longestPalindrome(self, s: str) -> str:
        palindrome=''

        for i in range(len(s)):
            len1=self.getlongestpalindrome(s,i,i)
            len2=self.getlongestpalindrome(s,i,i+1)
            if len(len1)>len(palindrome):
                palindrome=len1
            if len(len2)>len(palindrome):
                palindrome=len2
        return palindrome



    def getlongestpalindrome(self,s,l,r):
        while l>=0 and r<len(s) and s[l]==s[r]:
            l-=1
            r+=1
        return s[l+1:r]


#测试数据
s="babad"
solution=Solution()
print(solution.longestPalindrome(s))

s="cbbd"
solution=Solution()
print(solution.longestPalindrome(s))
